1. Field of the Invention
The present invention relates to data communications systems and, in particular, to methods and apparatus for implementing a cyclic redundancy check (CRC) calculation in a High Level Data Link Control (HDLC) module.
2. Discussion of the Prior Art
Communications between stations in a data transmission network occur through the transmission of a series, or "frame", of information characters, with adjacent frames being separated by explicit or implicit start-stop patterns. The use of a unique start pattern ("start delimiter") and a unique stop pattern ("end delimiter") allows the receiving station to identify the exact beginning and the exact end of each frame.
William Stallings, Local Networks, Third Edition, Macmillan Publishing Co., 1990, Chapter 2, provides an overview of communications architectures for computer networks. As discussed by Stallings, to support communications between computer stations in a network, additional hardware and software is required. Communications hardware is reasonably standard. However, when communications is desired among different types of computer stations, the software development effort can become formidable, since different computers use different data formats and data exchange conventions.
Since development of special communications software for each network application is clearly too costly to be practical, the alternative is to establish common communications standards and a general computer architecture that defines the communications tasks.
A well known technique for defining computer architecture is "layering", wherein the computer's communications functions are partitioned into a hierarchical set of layers. Each layer of a station performs a related subset of the functions required to communicate with another station on the network.
The Open Systems Interconnection (OSI) model is an architectural standard that defines seven hierarchical communications layers. Information exchange between stations on an OSI network is achieved by having corresponding layers in different stations communicate in accordance with an established set of rules, known as a protocol.
FIG. 1 shows computer stations A and B, each of which, consistent with the OSI architecture, contains the seven OSI communications layers. When computer station A has data to send to computer station B, it transfers the data to its application layer. The application layer appends an application header (AH) which contains control data needed by the application layer in computer station B. The data is then passed down through the layer hierarchy, with each layer appending its own control header for use by the corresponding layer in computer station B. The data link layer generally appends both a header (LH) and a trailer (LT). The data link layer data unit, i.e., a "frame", is then transmitted by the physical layer onto the physical transmission medium.
As indicated above, the physical layer generally provides only bit stream service, that is, it serves only to physically transmit or receive, in a bit-by-bit, or serial manner, the bits of the binary information frame to/from the transmission medium. It is the data link layer than utilizes its bit-oriented communications protocol to define the frame.
One such standard OSI bit-oriented data link protocol is the so-called High-Level Data Link Control (HDLC) protocol.
According to the HDLC protocol, and as shown in FIG. 2, information is transmitted onto the physical transmission medium in frames that consist of six fields. The FLAG field is used for synchronization, indicating the start and end of a frame (i.e., it serves as the frame start and end delimiters). The ADDRESS field identifies the destination station for the frame. The control field identifies the function and purpose of the frame. The DATA frame contains the information to be transmitted. The CRC frame is a frame check sequence field that uses a 16-bit cyclic redundancy check (CRC).
As discussed by Stallings, the HDLC CRC field is a function of the contents of the Address, Control and Data fields. It is generated by the transmitter station and again by the receiver station. If the result generated by the receiver station differs from the CRC field of the received frame, then a transmission error has occurred.
In the implementation of the CRC calculation, the information to be transmitted is treated as a single binary number. This number is divided by a unique prime binary number and the remainder of this division operation is entered in the CRC field of the HDLC frame. When the frame is received, the receiver station performs the same division using the same prime number and compares the calculated remainder with the received CRC frame.
In a CRC calculation, the most commonly used divisors are a 17-bit primary number, which produces a 16-bit remainder, and a 33-bit prime number, which produces a 32-bit remainder. Use of the smaller divisor results in less overhead.
In a HDLC module, the CRC is a 16-bit sequence. It is defined as the complement of the sum (modulo 2) of:
1) the remainder of EQU X.sup.k (X.sup.15 +X.sup.14 +X.sup.13. . . X.sup.2 +X+1)
divided (modulo 2) by the generator polynomial EQU X.sup.16 +X.sup.12 +X.sup.5 +`
where k is the number of bits in the frame existing between, but not including, the final bit of the opening FLAG and the first bit of the CRC, excluding bits inserted for transparency, and
2) the remainder after multiplication by X.sup.16 and then division (modulo 2) by the generator polynomial EQU X.sup.16 +X.sup.12 +X.sup.5 +`
of the content of the frame, existing between, but not including, the final bit of the opening FLAG and the first bit of the CRC, excluding bits inserted for transparency.
As a typical implementation, at the transmitter, the initial remainder of the division is preset to all 1s and is then modified by division by the generator polynomial, as described above, on the Address, Control and Data fields. The 1s complement of the resulting remainder is transmitted as the 16-bit HDLC CRC sequence.
At the receiver, the initial remainder is preset to all 1s and the serial incoming protected bits and the CRC, when divided by the generator polynomial will result in a remainder of 0001110100001111 (X.sup.15 through X.sup.0, respectively) in the absence of transmission errors. The CRC is transmitted to the line commencing with the coefficient of the highest term.
The CRC computation is the most critical ingredient of a HDLC handling module in terms of run-time performance. However, run-time performance of conventional HDLC CRC modules has become inadequate for many current applications.